package 剑指offer;

/**
 * @description: [1, 3, 5, 2, 2], 5, 3
 * @author: ywk
 * @date: 2020-10-20
 */
public class 返回第K大的数 {
    public static void main(String[] args) {
        int[] ints = {1, 3, 5, 1, 3, 88, 20, 11};
        int[] list = new int[ints.length];
        System.arraycopy(ints, 0, list, 0, ints.length);
        System.out.println(findKth(ints, 5, 5-3));
            quickSort(list, 0, list.length - 1);
        print(list);

    }

    public static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }

    //利用快速排序的思想
    public static int findKth(int[] a, int n, int K) {
        // write code here
        return findKth(a, 0, a.length - 1, K);
    }

    public static int findKth(int[] a, int start, int end, int k) {
        int pivot = getPivot(a, start, end);
        if (pivot > k) {
            return findKth(a, start, pivot-1, k);
        }
        if (pivot < k) {
            return findKth(a, pivot + 1, end, k);
        } else {
            return a[pivot];
        }
    }

    public static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int pivot = getPivot(arr, start, end);
            quickSort(arr, start, pivot);
            quickSort(arr, pivot + 1, end);
        }
    }

    private static int getPivot(int[] arr, int start, int end) {
        int key = arr[start];
        int low = start;
        int high = end;
        while (low < high) {
            while (low < high && arr[high] >= key) {
                --high;
            }
            while (low < high && arr[low] <= key) {
                ++low;
            }
            if (low < high) {
                swap(arr, low, high);//交换比枢轴小的记录到左端
            }
        }
        swap(arr, start, low);
        return low;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
